A wide range of applications in signal processing exhibits data that can be represented on vertices of graphs that describe a geometric structure of the data. These applications include social, energy, transportation and sensor networks, as well as synthetic and natural images, videos, and medical and hyper-spectral images.
One particular application is 3D video signal processing, where images often have different quality levels due to various acquisition and compression techniques applied to source signals. For example, changes of brightness or color can be produced by imaging sensors and circuitry of stereo cameras, or from shot noise. Conventional image enhancement techniques can be used to improve the quality of the images. Since depth map compression has become an integral part of 3D video formats, e.g., 3D-Advanced Video Coding (AVC) and 3D-High Efficiency Video Coding (HEVC), it is desirable to exploit depth information to enhance low quality images.
Graph signal processing tools have been used in conventional image processing applications. For example, a typical interpolation procedure uses a spectral graph, where an upsampling problem is formulated as a regularized least squares problem performed in the graph spectral domain. That approach has extended to depth image upsampling. A similar graph based method to enhance noisy stereo images uses depth information to generate a guide image. However, those methods suffer from high complexity due to the requirement of determining a full eigenvalue decomposition of very high dimensional data.
Another approach determines the graph spectral filter by means of a regularized, least squares problem with a regularization parameter. This approach has a disadvantage that the outcome of the filtering is highly sensitive to the choice of the regularization parameter.
An alternative approach, which avoids full eigendecompositions, uses a graph spectral filter approximated by polynomials. The filtering operation is performed by applying the polynomial as a function of a graph Laplacian matrix in the pixel domain. That approach restricts the filtering process to a predetermined fixed function, which may not be the best suitable for a variety of given signals.
Basics of Signals on Graphs
In graph signal processing, an undirected graph G=(V, E) includes a set of vertices, also called nodes, V={1, 2, . . . , N} connected by a set of edges E={(i, j, wij)}, i, jεV, where (i,j, wij) denotes an edge between nodes i and j associated with a weight wij≧0. A degree di of a node i is a sum of edge weights connected to the node i.
An adjacency matrix W of the graph is a symmetric N×N matrix having entries wij≧0, and a diagonal degree matrix is D:=diag{d1, d2, . . . , dN}. A graph Laplacian matrix L:=D−W is a positive semi-definite matrix, thus admitting an eigendecomposition L=UΛUT, where U is an orthogonal matrix with columns forming an orthonormal set of eigenvectors, and Λ=diag{λ1, . . . , λN} is a matrix made of corresponding eigenvalues all real.
The eigenvalues and eigenvectors of the Laplacian matrixes provide a spectral interpretation of graph signals, where the eigenvalues can be treated as graph Fourier frequencies, and the eigenvectors as generalized. Fourier modes.
A graph can be associated with an underlying image filter, conventionally used as one of the filter testing benchmarks. Specifically, for an input image {circumflex over (x)}in the conventionally filtered output image {circumflex over (x)}out can be written as,{circumflex over (x)}outD−1W{circumflex over (x)}in={circumflex over (x)}in−D−1L{circumflex over (x)}in.  (1)
Graph Spectral Filtering (GSF)  can be designed for image processing purposes in the graph spectral domain, where  is a diagonal matrix, typically given as =h(Λ), where h(λ) is a real valued function of a real variable λ, determining the filter. The corresponding graph filter H in the vertex domain can be expressed as,H=h(L)=UUT.  (2)
Basics of Graph Based Image Processing
For image processing applications, a pixel in an image can be treated as a node in a graph, while weights on edges connecting the nodes represent a measure of similarity of the pixels connected by the edges. As shown in FIG. 1A, in the context of graph based image processing, the vertices of the graph correspond to pixels in the image. FIG. 1A, shows a 4-connected simple graph that is defined before setting and applying graph based approaches for image denoising. Each pixel is connected only to its font immediate neighbors in, the image plane. All pixels within the image, or an image slice, share a single graph and are be processed within one graph spectral domain.
After the connection structure in the graph is defined, a weight is assigned for each graph edge. One approach is to assign bilateral weights, where the weights wij are defined by
                              w          ij                =                              exp            (                          -                                                                                                                                      p                        i                                            -                                              p                        j                                                                                                  2                                                  2                  ⁢                                      σ                    s                    2                                                                        )                    ⁢                                    exp              (                              -                                                                            (                                                                                                    x                                                          i                              ⁢                                                                                                                          ⁢                              n                                                                                ⁡                                                      [                            i                            ]                                                                          -                                                                              x                                                          i                              ⁢                                                                                                                          ⁢                              n                                                                                ⁡                                                      [                            j                            ]                                                                                              )                                        2                                                        2                    ⁢                                          σ                      r                      2                                                                                  )                        .                                              (        3        )            
The first exponential term is a spatial distance penalty, where pi refers to the pixel spatial location, and the second exponential term is an intensity distance penalty, where xin refers to an intensity value.